#pragma once

#include <compl.h>
#include <dbg.h>
#include <libapfsds.h>
typedef struct hnode
{
	struct hnode *next;
	word_t key;
	void *val;
} hnode_t;

typedef struct
{
	hnode_t **tbl;
	word_t size;
	word_t nums;
	word_t count;
} ALIGN(HDEF_CACHE_LINE_BYTES) htable_t;

static inline word_t hash_word(word_t key, word_t bits)
{
	word_t hash = (key * GOLDEN_RATIO); //>>(WORD_BIT-bits);
	//hash = hash*GOLDEN_RATIO_PRIME;
	return hash >> (WORD_WIDTH - bits);
}

static inline void *htable_init(htable_t *tbl, word_t hsize)
{
	// 不引入向量寄存器
	// memset(tbl->tbl, 0, hsize * sizeof(hnode_t *));

	for (word_t i = 0; i < hsize; i++){
		tbl->tbl[i] = 0;
	}
	return tbl;
}

#include "stdlib.h"
static inline void *htable_create(word_t hsize)
{
	htable_t *tbl = (htable_t *)malloc(sizeof(htable_t) + sizeof(hnode_t *) * hsize);
	tbl->size = hsize;
	tbl->tbl = (hnode_t **)((char *)tbl + sizeof(htable_t));
	tbl->nums = 0;
	tbl->count = 0;
	htable_init(tbl, tbl->size);
	return tbl;
}

static inline hnode_t *htable_search(htable_t *tbl, word_t key, hnode_t **pprev, word_t *pidx)
{
	word_t hsize = tbl->size;
	hnode_t **h = tbl->tbl;
	word_t idx = hash_word((word_t)key, WORD_WIDTH) & (hsize - 1);
	/* word_t i; */
	hnode_t *ret = NULL;
	hnode_t *cur;
	hnode_t *prev = NULL;

	*pprev = prev;

	*pidx = idx;
	if (!h[idx])
		return NULL;
	if (h[idx]->key == key)
	{
		ret = h[idx];
	}
	else
	{
		prev = h[idx];
		for (cur = h[idx]->next; cur; cur = cur->next)
		{
			if (cur->key == key)
			{
				*pprev = prev;
				ret = cur;
				break;
			}
			prev = cur;
		}
	}

	return ret;
}

/* NOTES: hsize必须是2的幂,避免求余运算带来的运算开销 */
/* 引入cur_cpu是将执行的随机性带入hash_map,以尽可能避免hash冲突 */
static inline bool_t htable_insert(htable_t *tbl, hnode_t *node)
{
	/* 连表法处理冲突 */
	// word_t hsize = tbl->size;
	hnode_t **h = tbl->tbl;
	word_t idx;
	/* word_t i; */
	hnode_t *prev;
	/* word_t iddx; */
	/* 如果找到了就不插入? */
	if(htable_search(tbl,node->key,&prev,&idx)){
		return FALSE;
	}
	node->next = h[idx];
	h[idx] = node;
	tbl->nums++;
	return TRUE;
}

static inline hnode_t *htable_remove(htable_t *tbl, word_t key)
{
	hnode_t *prev;
	hnode_t *ret;
	word_t idx;
	//printf("try to remove %llu\n",key);
	ret = htable_search(tbl, key, &prev, &idx);
	if (ret)
	{
		if (prev)
			prev->next = ret->next;
		else
		{
			tbl->tbl[idx] = ret->next;
		}
		tbl->nums--;
		//printf("remove success %llx\n",ret);
	}
	//else printf(" we can not find the key \n");
	return ret;
}

word_t htable_insert_cb(APFSDS_ARGLIST)
{
	PARAM_USED(arg2, arg3);
	word_t ret = 0;
	if ((arg0 != 0 ) && (arg1 != 0)){
		ret = htable_insert((htable_t *)arg0, (hnode_t *)arg1);
	}
	if(ret){
		ret = ++((htable_t *)arg0)->count;
	}
	else{
		fatal("!!!can not insert!\n");
	}
	return ret;
}

word_t htable_remove_cb(APFSDS_ARGLIST)
{
	PARAM_USED(arg2, arg3);
	if ((arg0 != 0))
		return (word_t)htable_remove((htable_t *)arg0, (word_t)arg1);
	return 0;
}
